import java.util.*;
public class LongestWord {
  public String longestWord(String[] words) {
        String res = "";
        Trie trie = new Trie();
        for(String s : words) {
            trie.insert(s);
        }
        for(String s : words) {
            if(trie.search(false, s, trie)) {
                res = s.length() > res.length() 
                    || (s.length() == res.length() && s.compareTo(res) < 0) ? s : res;
            }
        }
        return res;
    }

    public class Trie {
        Trie[] children;
        boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String s) {
            Trie node = this;
            for(int i = 0; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                if(node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        //回溯, 如果当前字符串由这组单词中的其他单词组合而成 返回true, flag用于排除字符串仅由自身组成
        public boolean search(boolean flag, String s, Trie trie) {
            Trie node = this;
            for(int i = 0; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                if(node.children[index] == null) {
                    return false;
                }
                if(node.children[index].isEnd && trie.search(true, s.substring(i + 1, s.length()), trie)) {
                    return true;
                }
                node = node.children[index];
            }
            return flag && node.isEnd;
        }
    }

  public static void main(String[] args) {
      LongestWord lw = new LongestWord();
      String[] words = {"ttaaaa","pp","tpa","kpaqkt","tktpqq","aqppatp"};
      System.out.println(lw.longestWord(words));
  }
}

// 给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

// 示例：

// 输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
// 输出： "dogwalker"
// 解释： "dogwalker"可由"dog"和"walker"组成。
// 提示：

// 0 <= len(words) <= 200
// 1 <= len(words[i]) <= 100